A. Course Contents: This course focuses on the design and analysis of algorithms and their applications.
1. Algorithmic fundamentals: mathematical foundations, growth of functions, recurrences (4 hrs)
2. Sorting and order statistic (6 hrs)
3. Data structures: binary search trees, RB trees, disjoint sets (5 hrs)
4. Advanced design and analysis techniques: dynamic programming, greedy algorithms, amortized analysis (12 hrs)
5. Graph algorithms: graph representations, searching, minimum spanning & Steiner trees, shortest paths, matching, network flow (12 hrs)
6. NP-completeness, computational complexity, and approximation algorithms (9 hrs)
7. General-purpose methods for combinatorial optimization: branch-and-bound, linear programming, simulated annealing, if time permits.
B. Text: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2nd Ed., McGraw Hill/The MIT Press, 2001. ISBN: 0-262-03293-7.
C. Grading:
Homework assignments: 25%
Two programming assignments: 20%
Two in-class tests: 55%.
D. Prerequisites: data structures and/or discrete mathematics.